import java.util.Scanner;

public class lomuto_partition {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        System.out.println("请输入队列个数：");
        int n = in.nextInt();

        int[] p = new int[n];//调用进程数据结构，设置进程数量

        System.out.println("请依次输入队列的值：");

        for (int i = 0; i < n; i++) {
            p[i] = in.nextInt();
        }

        System.out.println("队列如下：");
        for (int i = 0; i < n; i++) {
            System.out.print(p[i] + "\t");
        }

        System.out.println();

        int k=p.length;
        if(k%2==0){
            k=k/2;
        }
        else {
            k=k/2+1;
        }

        int left=0;
        int right=p.length-1;
        Quickselect(p,k,left,right);
    }

    public static int LomutoPartition(int[] A,int left,int right){
        int p=A[left];
        int s=left;
        for(int i=left+1;i<right;i++){
            if(A[i]<p){
                s=s+1;
                int m=A[s];
                A[s]=A[i];
                A[i]=m;
            }
        }
        int w=A[left];
        A[left]=A[s];
        A[s]=w;
        return s;
    }

    public static void Quickselect(int[] A,int k,int left,int right){
        int s=LomutoPartition(A,left,right);
        if(s>k-1){
            right=s-1;
            Quickselect(A,k,left,right);
        }
        else if(s<k-1){
            left=s+1;
            Quickselect(A,left+k-1-s,left,right);
        }
        else if(s==k-1){
            System.out.println("该数组的中值位于第"+k+"个，其值为："+A[s]);
        }
    }
}
